1. Field of the Invention
The present invention relates to a job scheduling system for solving scheduling problems such as a production programming, and in particular, to a scheduling system for generating restriction violating conditions or restriction satisfying conditions and properly using these conditions in later processes so as to effectively set out a schedule.
2. Description of the Related Art
Scheduling problems such as production programming include job shop scheduling problem.
In a job shop scheduling problem, each of n jobs is composed of m procedures. Each procedure is processed by one of m machines. Each machine cannot execute two or more procedures at the same time. Each procedure has a process time period, an available start time, and an end time. Procedures which compose one job are sequentially related. The start time of each procedure should be designated so that the total process time period becomes minimum.
The solution space of this scheduling problem tends to potentially become large due to the presence of many combinations. Thus, a simple search system cannot be used. However, in the apparent solution space, portions where solutions are not present can be sometimes found. Therefore, by properly using this technique, a solution can be effectively obtained.
Known techniques of this kind which are conventionally used are, (a) integer programming method, (b) branch and bound method, and (c) ATMS. Next, with respect to these techniques for solving a job scheduling problem, examples for minimizing the total process time period will be described.
(a) Integer Programming Method
In addition to variables with respect to the start time and end time of each procedure of each job, to represent a condition where two procedures are not processed by the same machine at the same time variables 0-1 with respect to the sequence of procedures executed by the same machine is introduced. However, this process results in increasing the number of variables. In addition, the computing time of the integer programming method tends to exponentially increase proportional to the number of variables. Thus, the computing time period becomes excessively long.
(b) Branch and Bound Method
In the condition where the start times of some of procedures have not been designated (namely in a partial schedule), the lower bound value of the total processing time period is obtained by using the total process time period of procedures which have not been scheduled (with respect to individual jobs and individual machines). When the lower bound value is larger than the value of the total process time period of the complete scheduling which has been-obtained, schedules which contain the partial schedule are removed from the search object. However, in this method, the process time periods of procedures which have not been scheduled are computed with respect to individual jobs or individual machines. Thus, the relation of a plurality of jobs cannot be considered. As a result, the lower bound value is underestimated. Therefore, the search range cannot be effectively narrowed.
(c) ATMS
The sequence of procedures executed by a particular machine is treated as a hypothesis. The combinations of hypotheses which cannot satisfy restriction conditions are stored. The combinations which contain these hypotheses are discarded. However, since the number of combinations of hypotheses becomes huge, the scale that can be dealt with is restricted.
The problems involved in these three methods are summarized as follows.
In the integer programming method, since the number of variables increases, the computing time exponentially increases. In the branch and bound method, the lower bound value is underestimated. On the other hand, in the ATMS, since the number of combinations of hypotheses increases, the computing time period increases.